package org.algorithm.wE1.链表;

import org.algorithm.common.ListNode;

import java.util.HashMap;
import java.util.Map;

/***
 *
 *  和为0 包括但不限定：    正整数之间想减和为0， 正负相加和为0
 *
 * 参考地址： https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
 */
public class 删除和为0的连续节点 {
    public static void main(String[] args) {
        int[] arr = {1,2,-3,3,1};
        ListNode node = ListNode.build(arr);
        ListNode.print(deleteSum0(node));
    }
    private static ListNode deleteSum0(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummyNode = new ListNode(0);

        dummyNode.next = head;
        ListNode newNode = dummyNode;
        Map<Integer,ListNode> sumMap = new HashMap<>();
        int sum = 0;
        while(newNode != null){
            sum += newNode.val;
//            System.out.print(sum+", ");
//            ListNode.print(newNode);
//            System.out.println();
            sumMap.put(sum,newNode);
            newNode = newNode.next;
        }
        System.out.println("=====================sumMap=======================");
        sumMap.forEach((k,v)->{
            System.out.println(k+", "+print(v));
        });
        System.out.println("=====================第2次遍历=======================");
        sum = 0;
        newNode = dummyNode;
        while(newNode != null){
            sum += newNode.val;
            System.out.print(sum+", ");
            ListNode.print(newNode);
            System.out.println();
            if(sumMap.get(sum) != newNode){
                newNode.next = sumMap.get(sum).next;
            }
            newNode = newNode.next;
        }
        System.out.println("=====================输出结果=======================");
        return dummyNode.next;
    }

    public static String print(ListNode node) {
        ListNode tmp = node;
        StringBuilder sb = new StringBuilder();
        while (tmp != null) {
            sb.append(tmp.val);
            tmp = tmp.next;
            if (tmp != null) {
                sb.append("->");
            }
        }
        return sb.toString();
    }
}
